LeetCode Hot100

/**
 * 暴力解法 - 时间复杂度 O(n²)
 * @param {number[]} nums - 输入数组
 * @param {number} target - 目标值
 * @returns {number[]} 满足条件的下标数组
 */
const twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
};

/**
 * 哈希表解法 - 时间复杂度 O(n)
 * @param {number[]} nums - 输入数组
 * @param {number} target - 目标值
 * @returns {number[]} 满足条件的下标数组
 */
const twoSum = function(nums, target) {
    const map = new Map(); // 存储值到下标的映射
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // 检查补数是否存在于哈希表中
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        
        // 将当前值存入哈希表
        map.set(nums[i], i);
    }
    
    return [];
};

// Definition for singly-linked list.
function ListNode(val, next) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
}

/** 使用递归的方式实现
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2, carry = 0) {
    // 默认值为0，没有默认值递归会出现问题
    if (l1 === null && l2 === null && carry === 0) {
        return null
        // 递归的边界条件
    }

    let sum = carry
    // 求和

    if (l1) {
        sum += l1.val
        l1 = l1.next
    }
    if (l2) {
        sum += l2.val
        l2 = l2.next
    }

    return 
    new ListNode(sum % 10, addTwoNumbers(l1, l2, Math.floor(sum / 10)))
    // Math.floor向下取整
}

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const hashMap = new Map()
    //遍历字符串数组以其中每项排序后的字符串为键，字符串加入数组作为值
    for (const item of strs) {
        const resort = item.split('').sort().join('')
        if (!hashMap.has(resort)) {
            hashMap.set(resort, [])
        }

        hashMap.get(resort).push(item)
    }
    return Array.from(hashMap.values())
}

const arr = [100, 4, 200, 1, 3, 2]

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
    const set = new Set(nums)
    let result = 0
    for (const item of set) {
        // 如果当前的数的前面还有比它小一个的数字
        // 那么他一定不是最长的
        if (set.has(item - 1)) {
            continue
        }
        let start = item + 1
        while (set.has(start)) {
            start++
        }

        result = Math.max(result, start - item)

        // 如果发现一条链的长度大于了数组长度的一般
        // 那么就不可有比它还大的链了，直接返回结果
        if (result >= nums.length) {
            break
        }
    }
    return result
}

console.log(longestConsecutive(arr))
// 4

const nums = [0, 1, 0, 3, 12]

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let stackSize = 0
    // 遍历每一个元素，如果非零就直接进入数组（可能会覆盖掉自己）
    // 0的位置不用考虑，等所有的非零元素进入后，再将0填入
    for (const num of nums) {
        if (num !== 0) {
            nums[stackSize] = num
            stackSize++
        }
    }
    nums.fill(0, stackSize)
}

moveZeroes(nums)
console.log(nums)
// [ 1, 3, 12, 0, 0 ]

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    let result = 0
    let lift = 0
    let right = height.length - 1
    // 这里要要减一，不然就越界
    while (lift < right) {
        let area = (right - lift) * Math.min(height[right], height[lift])
        result = Math.max(result, area)
        if (height[right] < height[lift]) {
            right--
        } else {
            lift++
        }
    }
    return result
}

console.log(maxArea(height))
// 49

nums = [-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4]

var threeSum = function (nums) {
    let result = []
    const twoSum = function (nums, target) {
        const map = new Map() // 存储值到下标的映射

        for (let i = 0; i < nums.length; i++) {
            const complement = target - nums[i]

            // 检查补数是否存在于哈希表中
            if (map.has(complement)) {
                return [nums[map.get(complement)], nums[i]]
            }

            // 将当前值存入哈希表
            map.set(nums[i], i)
        }

        return []
    }

    for (let index = 0; index < nums.length; index++) {
        let fixedSum = 0 - nums[index]
        // console.log(nums[index], 'fixedSum', fixedSum)

        let fixedArr = Array.from(nums)
        fixedArr.splice(index, 1)
        // console.log(fixedArr, nums)

        let res = twoSum(fixedArr, fixedSum)

        if (res.length !== 0) {
            // console.log('res:',res);

            res.push(nums[index])
            res.sort()

            result.push(res)
        }
    }
    const seen = new Set()

    return result.filter((item) => {
        const str = JSON.stringify(item)

        if (seen.has(str)) {
            return false
        }
        seen.add(str)
        return true
    })
}

console.log(threeSum(nums))
// [[-1, 0, 1], [-1, -1, 2], [-4, 1, 3], [-2, 0, 2], [-3, 1, 2], [-4, 0, 4]]
// 如果只有一种可能得情况下是完全没问题的，但是[-3, -1, 4]没有，因为在选中-3的情况下
// 只在剩余的数组中找到了最先出现的一对，但其实后面还有

nums = [0, 0, 0, 0, 0, 0, 0]
/** 灵神无敌好吧
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    nums.sort((a, b) => a - b)
    let result = []
    // console.log(nums);
    for (let i = 0; i < nums.length - 2; i++) {
        let j = i + 1
        let k = nums.length - 1
        if (i > 0 && nums[i] === nums[i - 1]) continue

        // 第一处优化，如果枚举的数字与剩下的最近两个就已经大于零了
        // 后面不可能比这种情况更小直接break
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break
        // 第二处
        if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0)
            continue
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] > 0) {
                k--
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                j++
            } else {
                result.push([nums[i], nums[j], nums[k]])
                for (j++; j < k && nums[j] === nums[j - 1]; j++) {}
                for (k--; j < k && nums[k] === nums[k + 1]; k--) {}
            }
        }
    }
    return result
}

console.log(threeSum(nums))

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let arrSum = height.reduce((acc, curr) => acc + curr)

    let lift = 0,
        right = height.length-1

    while (lift < right) {
        let min = Math.min(height[lift], height[right])
        // console.log(min);
        console.log(lift,right,height[lift], height[right],min)
        
        for (let i = lift; i < right; i++) {
            if (height[i] < min) {
                height[i] = min
            }
        }

        if (height[lift] < height[right]) {
            lift++
        } else {
            right--
        }
    }
    console.log(height)

    let sum = height.reduce((acc, curr) => acc + curr)
    return sum - arrSum
}

console.log(trap(height))
// 6

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let arrSum = height.reduce((acc, curr) => acc + curr)

    let lift = 0
    let right = height.length - 1

    let liftMax = height[lift]
    let rightMax = height[right]

    while (lift < right) {
        liftMax = Math.max(liftMax, height[lift])
        rightMax = Math.max(rightMax, height[right])

        if (liftMax < rightMax) {
            height[lift] = liftMax
            console.log(`将左侧index=${lift}的${height[lift]}设置为${liftMax}`)
            lift++
        } else {
            console.log(`将右侧index=${right}的${height[right]}设置为${rightMax}`)
            height[right] = rightMax
            right--
        }
    }
    console.log(height)

    let sum = height.reduce((acc, curr) => acc + curr)
    console.log(sum)

    return sum - arrSum
}

console.log(trap(height))
// 6

s = 'afddd'

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let lift = 0
    let right = lift

    let result = 0
    const seen = new Set()

    while (right < s.length) {
        if (seen.has(s[right])) {
            result = Math.max(result, right - lift)
            lift++
            right=lift
            seen.clear()
        } else {
            seen.add(s[right])
            right++
        }
    }
    result = Math.max(result, right - lift)
    return result
}

console.log(lengthOfLongestSubstring(s))
// 3

var lengthOfLongestSubstring = function(s) {
    let ans = 0;
    let left = 0;
    // 以字符为键，值为其数量
    const cnt = new Map(); 
    // 维护从下标 left 到下标 right 的字符
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        cnt.set(c, (cnt.get(c) ?? 0) + 1);
        while (cnt.get(c) > 1) { // 窗口内有重复字母
            cnt.set(s[left], cnt.get(s[left]) - 1); // 移除窗口左端点字母
            left++; // 缩小窗口
        }
        ans = Math.max(ans, right - left + 1); // 更新窗口长度最大值
    }
    return ans;
};

s = 'beeaaedcbc'
p = 'ee'

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    let result = []

    if (!s.includes(p)) {
        return result
    }

    let hash = new Set()
    let sublength = p.length
    let fixedSub = p.split('').sort().join('')
    // console.log(fixedSub)

    hash.add(fixedSub)

    for (let index = 0; index < s.length - sublength + 1; index++) {
        let res = s.slice(index, sublength + index)
        // console.log(s, '->', res)
        let fixedRes = res.split('').sort().join('')

        if (hash.has(fixedRes)) {
            result.push(index)
        }
    }

    return result
}

console.log(findAnagrams(s, p))
// [ 1 ]

s = 'afdsa'
p = 'a'

var findAnagrams = function (s, p) {
    const ans = []
    const cntP = new Array(26).fill(0) // 统计 p 的每种字母的出现次数
    const cntS = new Array(26).fill(0) // 统计 s 的长为 len(p) 的子串 s' 的每种字母的出现次数

    for (const item of p) {
        cntP[item.charCodeAt() - 'a'.charCodeAt()]++
        // console.log(item.charCodeAt())
    }
console.log(cntP);

    for (let right = 0; right < s.length; right++) {
        cntS[s[right].charCodeAt() - 'a'.charCodeAt()]++
        let left = right - p.length + 1

        if (left < 0) {
            continue
        }

        if (JSON.stringify(cntP) === JSON.stringify(cntS)) {
            ans.push(left)
        }
        cntS[s[left].charCodeAt() - 'a'.charCodeAt()]--
    }

    return ans
}

console.log(findAnagrams(s, p))
// [(0, 4)]

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    let result = 0
    const leftSum = []
    let sum = 0
    for (let index = 0; index < nums.length; index++) {
        sum += nums[index]

        leftSum[index] = sum
    }
    console.log(leftSum)

    let left = 0
    let right = 0

    while (right<nums.length) {
        if (leftSum[right] - leftSum[left]+nums[left] < k) {
            console.log(
                `当前小于k，右侧为${right}，左侧${left}，值${
                    leftSum[right] - leftSum[left]+nums[left]
                }`
            )

            right++
        } else if (leftSum[right] - leftSum[left]+nums[left] > k) {
            console.log(
                `当前大于k，右侧为${right}，左侧${left}，值${
                    leftSum[right] - leftSum[left]+nums[left]
                }`
            )
            left++
        } else if ((leftSum[right] - leftSum[left] + nums[left]) == k) {
            console.log(
                `当前等于k，右侧为${right}，左侧${left}，值${
                    leftSum[right] - leftSum[left] + nums[left]
                }`
            )
            result++
            right++
        } else {
            right++
        }
    }

    return result
}

nums = [-1, -1, 1]
k = 0

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    let result = 0
    const leftSum = []
    let sum = 0
    for (let index = 0; index < nums.length; index++) {
        sum += nums[index]

        leftSum[index] = sum
    }
    console.log(leftSum)

    for (let left = 0; left < nums.length; left++) {
        for (let right = left; right < nums.length; right++){
            if (leftSum[right] - leftSum[left] + nums[left] == k) {
                result++
            }
        }
    }

    return result
}

console.log(subarraySum(nums, k))

nums = [1, -1, 0]
k = 0

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    const n = nums.length
    const s = Array(n + 1).fill(0)

    // 前缀的第一项一定是0，n长的数组的前缀有n+1项
    for (let i = 0; i < n; i++) {
        s[i + 1] = s[i] + nums[i]
    }
    console.log(s)
    // [ 0, 1, 3, 6 ]

    let ans = 0
    const cnt = new Map()
    for (const sj of s) {
        // ??空值合并 如果第一个参数不是null/undefined，则??返回第一个参数。否则，返回第二个参数。
        // ???这里是什么万银
        ans += cnt.get(sj - k) ?? 0

        console.log(`${sj}-${k}，在`)
        console.log(cnt)
        console.log(`中寻找s[i]=${sj - k},${cnt.get(sj - k) ?? '没有'}`)

        // 这里使用Set实现不是更好吗，这样的写法我感觉有点迷惑
        // 这里+1是干嘛？加一就是将前方出现的次数记录下来了
        cnt.set(sj, (cnt.get(sj) ?? 0) + 1)
        console.log(`将${sj}加入`)
    }
    console.log(cnt)

    return ans
}

console.log(subarraySum(nums, k))

nums = [1, 3, 1, 2, 0, 5]
k = 3

var maxSlidingWindow = function (nums, k) {
    const result = []
    const queue = [] // 存储索引
    for (let right = 0; right < nums.length; right++) {
        // 维护队列递减性：弹出所有小于当前元素的队列尾索引
        while (
            queue.length > 0 &&
            nums[right] >= nums[queue[queue.length - 1]]
        ) {
            queue.pop()
        }
        queue.push(right)

        // 检查队列头索引是否超出窗口左边界
        if (queue[0] <= right - k) {
            queue.shift()
        }

        // 当窗口大小达到k时，记录最大值
        if (right >= k - 1) {
            result.push(nums[queue[0]])
        }
    }
    return result
}

console.log('result:', maxSlidingWindow(nums, k))

s = 'ADOBECODEBANC'
t = 'ABC'

function isCovered(cntS, cntT) {
    for (let i = 'A'.charCodeAt(0); i <= 'Z'.charCodeAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false
        }
    }
    for (let i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false
        }
    }
    return true
}

var minWindow = function (s, t) {
    const cntS = Array(128).fill(0) // s 子串字母的出现次数
    const cntT = Array(128).fill(0) // t 中字母的出现次数
    for (const c of t) {
        cntT[c.codePointAt(0)]++
    }

    let ansLeft = -1
    let ansRight = s.length
    let left = 0
    for (let right = 0; right < s.length; right++) {
        // 移动子串右端点
        cntS[s[right].codePointAt(0)]++ // 右端点字母移入子串
        while (isCovered(cntS, cntT)) {
            // 涵盖
            if (right - left < ansRight - ansLeft) {
                // 找到更短的子串
                ansLeft = left // 记录此时的左右端点
                ansRight = right
            }
            cntS[s[left].codePointAt(0)]-- // 左端点字母移出子串
            left++
        }
    }
    return ansLeft < 0 ? '' : s.substring(ansLeft, ansRight + 1)
}

console.log('result:', minWindow(s, t))

let nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

let nums2 = [-1, 0, -2]
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let minSum = 0
    let curSum = 0
    let result = []

    for (let index = 0; index < nums.length; index++) {
        minSum = Math.min(minSum, curSum)

        curSum += nums[index]

        result.push(curSum - minSum)

        console.log(`前缀和:${curSum}最小和:${minSum}值:${result}`)
    }

    return Math.max(...result)
}
console.log('result:', maxSubArray(nums2))

let matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const rotate = function (matrix) {
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < i; j++) {
            const tmp = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = tmp
        }
    }

    for (const element of matrix) {
        element.reverse()
    }
}

rotate(matrix)
console.log('result:', matrix)
// result: [ [ 7, 4, 1 ], [ 8, 5, 2 ], [ 9, 6, 3 ] ]

let matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const rotate = function (matrix) {
    const DIRS = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
    ]
    const m = matrix.length
    const n = matrix[0].length
    const result = Array(m * n)

    let i = 0,
        j = 0,
        di = 0

    for (let k = 0; k < m * n; k++) {
        result[k] = matrix[i][j]
        matrix[i][j] = Infinity

        // 判断下一个位置，越界就换方向
        const i_next = i + DIRS[di][0]
        const j_next = j + DIRS[di][1]
        if (
            i_next < 0 ||
            i_next >= m ||
            j_next < 0 ||
            j_next >= n ||
            matrix[i_next][j_next] === Infinity
        ) {
            di = (di + 1) % 4
        }

        i += DIRS[di][0]
        j += DIRS[di][1]
    }

    return result
}

console.log('result:', rotate(matrix))
// result: [ [ 7, 4, 1 ], [ 8, 5, 2 ], [ 9, 6, 3 ] ]

let nums = [7, 8, 9, 11, 12]
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
    let min = 0
    let max = 0
    const set = new Set()

    for (item of nums) {
        min = Math.min(min, item)
        max = Math.max(max, item)
        set.add(item)
    }
    console.log(min, max, set)

    for (let i = 1; i < max + 1; i++){
        if (!set.has(i)) {
            return i
        }
    }

    return max+1
}

console.log('result:', firstMissingPositive(nums))
// result: 1

var firstMissingPositive = function(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        // 如果当前学生的学号在 [1,n] 中，但（真身）没有坐在正确的座位上
        while (1 <= nums[i] && nums[i] <= n && nums[i] !== nums[nums[i] - 1]) {
            // 那么就交换 nums[i] 和 nums[j]，其中 j 是 i 的学号
            const j = nums[i] - 1; // 减一是因为数组下标从 0 开始
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }

    // 找第一个学号与座位编号不匹配的学生
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    // 所有学生都坐在正确的座位上
    return n + 1;
};

var searchMatrix = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (matrix[i][j] === target) {
            return true; // 找到 target
        }
        if (matrix[i][j] < target) {
            i++; // 这一行剩余元素全部小于 target，排除
        } else {
            j--; // 这一列剩余元素全部大于 target，排除
        }
    }
    return false;
};

let head = [1, 2, 3, 4, 5]

function ListNode(val, next) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
}
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    let pre = null,
        cur = head
    while (cur) {
        const nxt = cur.next
        cur.next = pre // 把 cur 插在 pre 链表的前面（头插法）
        pre = cur // 将头转换为刚插入的结点
        cur = nxt
    }
    return pre
}

console.log('result:', reverseList(head))

/**
 * @param {number} n
 * @return {number}
 */

// 使用额外的空间来减少同样的计算
const map = new Map()
var climbStairs = function (n) {
    if (n === 0 || n === 1) {
        return 1
    } else if (n === 2) {
        return 2
    }

    if (map.has(n)) {
        console.log('has', map.get(n))

        return map.get(n)
    } else {
        const temp = climbStairs(n - 1) + climbStairs(n - 2)
        map.set(n, temp)
        return temp
    }
}

console.log(climbStairs(10))
// has 3
// has 5
// has 8
// has 13
// has 21
// has

// 阶乘函数
const map1 = new Map()
function factorial(n) {
    if (n < 0) return NaN
    if (n === 0 || n === 1) return 1

    if (map1.has(n)) {
        return map1.get(n)
    } else {
        let result = 1
        for (let i = 2; i <= n; i++) {
            result *= i
        }
        map1.set(n.result)
        return result
    }
}

// 杨辉三角通项公式
function yanghuiTerm(n, k) {
    return factorial(n) / (factorial(k) * factorial(n - k))
}

// 生成杨辉三角的某一行
function generateYanghuiRow(rowIndex) {
    const row = []
    for (let k = 0; k <= rowIndex; k++) {
        row.push(yanghuiTerm(rowIndex, k))
    }
    return row
}

var generate = function (numRows) {
    const result = []
    for (let index = 0; index < numRows; index++) {
        result.push(generateYanghuiRow(index))
    }
    return result
}

console.log(generate(23))
// [ [ 1 ], [ 1, 1 ], [ 1, 2, 1 ], [ 1, 3, 3, 1 ], [ 1, 4, 6, 4, 1 ] ]

var generate = function(numRows) {
    const c = Array(numRows);
    for (let i = 0; i < numRows; i++) {
        c[i] = Array(i + 1);
        c[i][0] = c[i][i] = 1;
        for (let j = 1; j < i; j++) {
            // 左上方的数 + 正上方的数
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    return c;
};

 /**
 * @param {number[]} nums
 * @return {number}
 */

var rob = function (nums) {
    const len = nums.length
    
	// 使用缓存减少重复的计算
    const map = new Map()

    function dfs(i) {
        if (i < 0) {
            return 0
        }
        if (map.has(i)) {
            return map.get(i)
        } else {
            const t = Math.max(dfs(i - 1), dfs(i - 2) + nums[i])
            map.set(i, t)
            return t
        }
    }
    return dfs(len - 1)
}

class LRUCatch {
    constructor(capacity, map = new Map()) {
        this.capacity = capacity
        this.map = map
    }

    get(key) {
        if (this.map.has(key)) {
            let tempValue = this.map.get(key)
            this.map.delete(key)
            this.map.set(key, tempValue)
            return tempValue
        }
        return undefined
    }

    set(key, value) {
        if (this.map.has(key)) {
            this.map.delete(key)
        } else if (this.map.size >= this.capacity) {
            this.map.delete(this.map.keys().next().value)
        }
        this.map.set(key, value)
    }
}

var detectCycle = function (head) {
    if (!head) return null

    let slow = head,
        fast = head

    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next

        if (slow === fast) break
    }

    if (!fast || !fast.next) return null

    let slow2 = head
    while (slow2 !== slow) {
        slow = slow.next
        slow2 = slow2.next
    }
    return slow
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    if (!list1 && !list2) return null

    let p1 = list1
    let p2 = list2
    let res = []

    while (p1 && p2) {
        if (p1.val >= p2.val) {
            res.push(p2.val)
            p2 = p2.next
        } else {
            res.push(p1.val)
            p1 = p1.next
        }
    }

    // 将非空的指针的剩余部分接上
    let p3 = p1 || p2

    while (p3) {
        res.push(p3.val)
        p3 = p3.next
    }

    return res
}

function mergeTwoLists(list1, list2) {
    const dummy = new ListNode(); // 用哨兵节点简化代码逻辑
    let cur = dummy; // cur 指向新链表的末尾
    while (list1 && list2) {
        if (list1.val < list2.val) {
            cur.next = list1; // 把 list1 加到新链表中
            list1 = list1.next;
        } else { // 注：相等的情况加哪个节点都是可以的
            cur.next = list2; // 把 list2 加到新链表中
            list2 = list2.next;
        }
        cur = cur.next;
    }
    cur.next = list1 ?? list2; // 拼接剩余链表
    return dummy.next;
}

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    let p1 = head
    let p2 = head

    for (let i = 0; i < n; i++) {
        p1 = p1.next
    }

    // 特殊的，在这种情况下，需要移除的就是第一个节点，直接返回head.next就可以了
    if (p1 === null) {
        return p2.next
    }

    while (p1.next) {
        p1 = p1.next
        p2 = p2.next
    }

    p2.next = p2.next.next

    return head
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
    if (head === null || head.next === null) {
        return head
    }

    let p0 = new ListNode(0, head)
    p0.next = head
    let p1 = head
    let p2 = p1.next

    let newHead = head
    let haveSwapped = false
    let tempHead = head.next

    while (p1 && p1.next) {
        p0.next = p2
        p1.next = p2.next
        p2.next = p1

        if (!haveSwapped) {
            newHead = tempHead
        }

        if (p1.next && p2.next.next.next) {
            p0 = p0.next.next
            p1 = p1.next
            p2 = p2.next.next.next
        } else {
            break
        }
    }

    return newHead
}

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const swap666 = (start, k) => {
    if (!start.next || !start || k === 1) return 0

    let end = start
    let nextStart = start.next

    for (let i = 0; i < k - 1; i++) {
        if (!end.next) return 0
        end = end.next
    }

    for (let i = 0; i < k - 1; i++) {
        start.next = end.next
        end.next = start
        start = nextStart
        nextStart = nextStart.next
    }
    return end
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
    if (head === null || head.next === null) {
        return head
    }

    let p0 = new ListNode(0, head)
    p0.next = head
    let p1 = head
    let p2 = p1.next

    let newHead = head
    let haveSwapped = false
    let tempHead = head.next

    while (p1 && p1.next) {
        p0.next = p2
        p1.next = p2.next
        p2.next = p1

        if (!haveSwapped) {
            newHead = tempHead
        }

        if (p1.next && p2.next.next.next) {
            p0 = p0.next.next
            p1 = p1.next
            p2 = p2.next.next.next
        } else {
            break
        }
    }

    return newHead
}

var reverseKGroup = function (head, k) {
    if (k === 1) return head
    if (k === 2) {
        return swapPairs(head)
    }
    let pre = new ListNode(0, head)
    let start = head

    while (1) {
        let end = swap666(start, k)
        if (pre.next === head) {
            pre.next = end
        }
        for (let i = 0; i < k - 1; i++) {
            if (start.next === null) return pre.next
            start = start.next
        }
    }

    return pre.next
}

var reverseKGroup = function(head, k) {
    let n = 0;
    for (let cur = head; cur; cur = cur.next) {
        n++;
    }

    const dummy = new ListNode(0, head);
    let p0 = dummy;
    let pre = null;
    let cur = head;

    // k 个一组处理
    for (; n >= k; n -= k) {
        for (let i = 0; i < k; i++) {
            const nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        
        const nxt = p0.next;
        p0.next.next = cur;
        p0.next = pre;
        p0 = nxt;
    }
    return dummy.next;
};

function getMiddleNode(head) {
    if (!head) return
    let fast = head
    let slow = head
    let pre = head

    while (fast && fast.next) {
        pre = slow
        slow = slow.next
        fast = fast.next.next
    }

    // 将前后两个链表断开
    pre.next = null

    return slow
}

// 21. 合并两个有序链表（双指针）
function mergeTwoLists(list1, list2) {
    const dummy = new ListNode(); // 用哨兵节点简化代码逻辑
    let cur = dummy; // cur 指向新链表的末尾
    while (list1 && list2) {
        if (list1.val < list2.val) {
            cur.next = list1; // 把 list1 加到新链表中
            list1 = list1.next;
        } else { // 注：相等的情况加哪个节点都是可以的
            cur.next = list2; // 把 list2 加到新链表中
            list2 = list2.next;
        }
        cur = cur.next;
    }
    cur.next = list1 ?? list2; // 拼接剩余链表
    return dummy.next;
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
    // 分治
    if (head === null || head.next === null) return head
    let middleNode = getMiddleNode(head)
    middleNode = sortList(middleNode)
    head = sortList(head)
    return mergeTwoLists(middleNode, head)
}